package com.yuzou.十月力扣;

public class 回文子串统计 {
    public static void main(String[] args) {
        String s = "abc";
        System.out.println(countSubstrings(s));
    }
    public static int countSubstrings(String s) {
        int n = s.length(),ans = 0;
        boolean[][] dp = new boolean[n+1][n+1];
        for(int i = n - 1;i >= 0;i--) {
            for(int j = i;j < n;j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i <= 2) {
                        dp[i][j] = true;
                        ans++;
                    }else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
}
